package day190813;

import java.util.HashSet;
import java.util.List;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/13 下午 04:01
 */
public class DeepReturn {

    // 回溯算法实现。注意：我把输入的变量都定义成了成员变量。
    int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中
    int[] weight = {2, 2, 4, 6, 3};  // 物品重量
    int n = 5; // 物品个数
    int w = 9; // 背包承受的最大重量

    public void f(int i, int cw) { // 调用 f(0, 0)
        if (cw == w || i == n) { // cw==w 表示装满了，i==n 表示物品都考察完了
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        f(i + 1, cw); // 选择不装第 i 个物品
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]); // 选择装第 i 个物品
        }
    }

    public int knapsack2(int[] items, int n, int w) {
        boolean[] states = new boolean[w + 1]; // 默认值 false
        states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
        if (items[0] <= w) {
            states[items[0]] = true;
        }
        for (int i = 1; i < n; ++i) { // 动态规划
            for (int j = w - items[i]; j >= 0; --j) {// 把第 i 个物品放入背包
                if (states[j] == true) {
                    states[j + items[i]] = true;
                }
            }
        }
        for (int i = w; i >= 0; --i) { // 输出结果
            if (states[i] == true) {
                return i;
            }
        }
        return 0;
    }

    public int knapsack3(int[] weight, int[] value, int n, int w) {
        int[][] states = new int[n][w + 1];
        for (int i = 0; i < n; ++i) { // 初始化 states
            for (int j = 0; j < w + 1; ++j) {
                states[i][j] = -1;
            }
        }
        states[0][0] = 0;
        if (weight[0] <= w) {
            states[0][weight[0]] = value[0];
        }
        for (int i = 1; i < n; ++i) { // 动态规划，状态转移
            for (int j = 0; j <= w; ++j) { // 不选择第 i 个物品
                if (states[i - 1][j] >= 0) states[i][j] = states[i - 1][j];
            }
            for (int j = 0; j <= w - weight[i]; ++j) { // 选择第 i 个物品
                if (states[i - 1][j] >= 0) {
                    int v = states[i - 1][j] + value[i];
                    if (v > states[i][j + weight[i]]) {
                        states[i][j + weight[i]] = v;
                    }
                }
            }
        }
        // 找出最大值
        int maxvalue = -1;
        for (int j = 0; j <= w; ++j) {
            if (states[n - 1][j] > maxvalue) {
                maxvalue = states[n - 1][j];
            }
        }
        return maxvalue;
    }

    public int knapsack4(int[] weight, int[] value, int n, int w) {
        int[] states = new int[w + 1];
        for (int i = 0; i <= w; ++i) { // 初始化 states
            states[i] = -1;
        }
        states[0] = 0;
        if (weight[0] <= w) {
            states[weight[0]] = value[0];
        }
        for (int i = 1; i < n; ++i) { // 动态规划，状态转移
            for (int j = w - weight[i]; j >= 0; --j) { // 选择第 i 个物品
                if (states[j] >= 0) {
                    int v = states[j] + value[i];
                    if (v > states[j + weight[i]]) {
                        states[j + weight[i]] = v;
                    }
                }
            }
        }
        // 找出最大值
        int maxvalue = -1;
        for (int j = w; j > -1; --j) {
            if (states[j] > maxvalue) {
                maxvalue = states[j];
            }
        }
        return maxvalue;
    }

    int[] value = {3, 4, 8, 9, 6}; // 物品的价值





    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public int uniquePaths2(int m, int n) {
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = 1;
            } else {
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 0) {
                dp[0][i] = 1;
            } else {
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[j] = j == 0? grid[i][j] : grid[i][j] + dp[j - 1];
                } else if (j == 0) {
                    dp[j] = grid[i][j] + dp[j];
                } else {
                    dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[n - 1];
    }

    public int minPathSum2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i] = dp[i] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(grid[i][j] + dp[j] , grid[i][j] + dp[j - 1]);
            }
        }
        return dp[n - 1];
    }

    public int minPathSum3(int[][] grid) {
        int[] dp = new int[grid[0].length];
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if(i == grid.length - 1 && j != grid[0].length - 1) {
                    dp[j] = grid[i][j] +  dp[j + 1];
                } else if(j == grid[0].length - 1 && i != grid.length - 1) {
                    dp[j] = grid[i][j] + dp[j];
                } else if(j != grid[0].length - 1 && i != grid.length - 1) {
                    dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
                } else {
                    dp[j] = grid[i][j];
                }
            }
        }
        return dp[0];
    }

    /**
     * 使用动态规划法获取给定金额下最小的硬币数量
     *
     * @param coinVal
     * 硬币值数组
     * @param total
     * 给定金额
     * @return 给定金额下最小的硬币数量
     */
    public int getLeastCoinNumByDP(int[] coinVal, int total) {
        // coinNum存放的是每个对应金额下最少硬币的最优解
        int[] coinNum = new int[total + 1];
        coinNum[0] = 0;
        //初始化coinNum数组，硬币值数组对应的值的硬币数量都为1
        for (int i = 0; i < coinVal.length; i++) {
            coinNum[coinVal[i]] = 1;
        }

        for (int i = 1; i <= total; i++) {
            if (coinNum[i] == 0) {
                // 获取每个i对应的最小硬币数值
                int minTemp = Integer.MAX_VALUE;
                for (int j = 0; j < coinVal.length; j++) {
                    if (i - coinVal[j] > 0) {
//                        int v1 = coinNum[i - coinVal[j]] + 1;
//                        if (v1 < minTemp) {
//                            minTemp = v1;
//                        }
                        minTemp = Math.min(coinNum[i - coinVal[j]] + 1, minTemp);
                    }
                }
                coinNum[i] = minTemp;
            }
        }
        return coinNum[total];
    }

    public int numDecodings(String s) {
        int length = s.length();
        if (length == 0) {
            return 0;
        }
        if (s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[length + 1];
        dp[0] = 1;
        for (int j = 0; j < length; j++) {
            if (s.charAt(j) != '0') {
                dp[j + 1] = dp[j];
            } else {
                dp[j] = 0;
            }
            if (j > 0 && (s.charAt(j - 1) == '1' || s.charAt(j - 1) == '2' && s.charAt(j) < '7')) {
                dp[j + 1] = dp[j + 1] + dp[j - 1];
            }
        }
        return dp[length];
    }

//    public static void main(String[] args) {
//        DeepReturn aReturn = new DeepReturn();
////        aReturn.f(0, 0);
////        aReturn.knapsack2(aReturn.weight, aReturn.weight.length, 9);
////        aReturn.knapsack4(aReturn.weight, aReturn.value, aReturn.weight.length, 9);
////        int[] coin = new int[]{1 ,3, 5};
////        int leastCoinNumByDP = aReturn.getLeastCoinNumByDP(coin, 9);
//        int[][] ints = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
//        List<Integer> list1 = Arrays.asList(-1);
//        List<Integer> list2 = Arrays.asList(2, 3);
//        List<Integer> list3 = Arrays.asList(1, -1, -3);
////        List<Integer> list4 = Arrays.asList(4, 1, 8, 3);
//        List<List<Integer>> list = new ArrayList<>();
//        list.add(list1);
//        list.add(list2);
//        list.add(list3);
////        list.add(list4);
//
//        aReturn.minimumTotal(list);
//    }


    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.get(triangle.size() - 1).size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[j] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

     char[] a = "mitcmu".toCharArray();
     char[] b = "mtacnu".toCharArray();
     int n1 = 6;
     int m1 = 6;

//    public static void main(String[] args) {
//        DeepReturn aReturn = new DeepReturn();
//        aReturn.lwstDP(aReturn.a, aReturn.n1, aReturn.b, aReturn.m1);
//    }

    public int lwstDP(char[] a, int n, char[] b, int m) {
        int len = Math.max(a.length, b.length);
        int[] minDist = new int[len];
//        for (int j = 0; j < m; ++j) { // 初始化第 0 行:a[0..0] 与 b[0..j] 的编辑距离
//            if (a[0] == b[j]) {
//                minDist[0][j] = j;
//            } else if (j != 0) {
//                minDist[0][j] = minDist[0][j-1]+1;
//            } else {
//                minDist[0][j] = 1;
//            }
//        }
//        for (int i = 0; i < n; ++i) { // 初始化第 0 列:a[0..i] 与 b[0..0] 的编辑距离
//            if (a[i] == b[0]) {
//                minDist[i][0] = i;
//            } else if (i != 0) {
//                minDist[i][0] = minDist[i-1][0]+1;
//            } else {
//                minDist[i][0] = 1;
//            }
//        }
        minDist[0] = a[0] == b[0] ? 0 : 1;
        for (int i = 0; i < n; ++i) { // 按行填表
            for (int j = m - 1; j >= 1; --j) {
                if (a[i] == b[j]) {
                    minDist[j] = min(
                            minDist[j]+1, minDist[j-1]+1, minDist[j-1]);
                } else {
                    minDist[j] = min(
                            minDist[j]+1, minDist[j-1]+1, minDist[j-1]+1);
                }
            }
        }
        return minDist[len-1];
    }

    private int min(int x, int y, int z) {
        int minv = Integer.MAX_VALUE;
        if (x < minv) {
            minv = x;
        }
        if (y < minv) {
            minv = y;
        }
        if (z < minv) {
            minv = z;
        }
        return minv;
    }

    public int maxProduct(int[] nums) {
        int maxVal = Integer.MIN_VALUE, iMax = 1, iMin = 1;
        for (int num : nums) {
            if (num < 0) {
                int temp = iMax;
                iMax = iMin;
                iMin = temp;
            }
            iMax = Math.max(num * iMax, num);
            iMin = Math.min(num * iMin, num);

            maxVal = Math.max(iMax, maxVal);
        }
        return maxVal;
    }

    public static void main(String[] args) {
        DeepReturn aReturn = new DeepReturn();
        aReturn.rob(new int[]{2, 1, 1, 2});
    }

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[1];
        dp[1] = Math.max(nums[2], nums[3]);
        for (int i = 3; i < nums.length; i++) {
            dp[i - 1] = Math.max(dp[i - 2], nums[i] + dp[i - 3]);
        }
        int[] dp2 = new int[nums.length];
        dp2[0] = nums[0];
        dp2[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length - 1; i++) {
            dp2[i] = Math.max(dp2[i - 1], nums[i] + dp2[i - 2]);
        }
        return Math.max(dp[nums.length - 2], dp2[nums.length - 2]);
    }

}